
\begin{frame}\frametitle{Optimierungen: Diamond Property}
\vspace{-1cm}
\includegraphics<1>[scale=0.6]{../../documentation/images/diamondProperty.pdf}
\vspace{-2cm}
\begin{itemize}
\item Für jede in Frage kommende Kante betrachte die angrenzenden gleichschenklig dreieckigen Regionen, bei denen der Winkel $\beta$ mit der Kante $\frac{\pi}{8}$ beträgt. \small{[Das/Joseph]}\normalsize
\item Sind beide Dreiecke nicht leer, kann die Kante nicht in MWT sein.
\item Diese Kanten werden bereits bei der Erzeugung aussortiert.
\item Später wurde der Winkel auf $\frac{\pi}{4.6}$ verbessert. \small{[Drysdale/McElfresh/Snoeyink]}
\end{itemize} 
\end{frame}

\begin{frame}\frametitle{Optimierungen: Datenstrukturen}
\includegraphics<1>[scale=0.6]{../../documentation/images/trianglesLeftRight.pdf}
\begin{itemize}
\item Jede Kante hat zwei Listen für angrenzende Dreiecke: eine für die linken, eine für die rechten Dreiecke.
\item Diese Dreiecke werden während der Vorverarbeitung aus allen in Frage kommenden Kanten erzeugt.
\end{itemize} 
\end{frame}

\begin{frame}\frametitle{Optimierungen: Datenstrukturen}
\includegraphics<1>[scale=0.6]{../../documentation/images/trianglesLeftRight.pdf}
\begin{itemize}
\item Der LMT-Algorithmus prüft für jede Kante für alle Paarungen von Dreiecken, ob das Minimalitätskriterium erfüllt wird.
\item Bereits überprüfte Paarungen, die das Minimalitätskriterium verletzen, brauchen nie wieder überprüft zu werden.
\item Folgerung: In späteren Durchgängen, beginne für jede Kante die Überprüfung mit der Dreieckspaarung, die im letzten Durchgang das Minimalitätskriterium erfüllt hat.
\item Zwei Fälle treten auf:
\begin{itemize}
\item Diese Paarung existiert noch. Die Prüfung bricht sofort wieder ab.
\item Mindestens eines der beiden Dreiecke wurde gelöscht. Weitere Paarungen müssen geprüft werden.
\end{itemize}
\end{itemize} 
\end{frame}


\begin{frame}\frametitle{Optimierungen: Datenstrukturen}
\includegraphics<1>[scale=0.5]{../../documentation/images/trianglesLeftRightList.pdf}
\begin{itemize}
\item trianglesLeft und trianglesRight sind als verkettete Listen implementiert.
\item Dabei wird auf die zuletzt geprüfte Paarung gezeigt.
\item Was passiert, wenn zum Beispiel Dreieck 1 von einem anderen Teil des Algorithmus gelöscht wird?
\end{itemize}
\end{frame}


\begin{frame}\frametitle{Optimierungen: Datenstrukturen}
\includegraphics<1>[scale=0.45]{../../documentation/images/trianglesLeftRightListIterator.pdf}
\begin{itemize}
\item Jedes Element \textit{n} der verketteten Listen trianglesLeft, trianglesRight verwaltet Verweise auf alle Kanten, die auf dieses Element zeigen.
\item Wird \textit{n} aus der verketteten Liste gelöscht, werden automatisch alle auf dieses Element verweisenden Kanten auf den Nachfolger weitergeleitet.
\item Das erlaubt es uns, einen Iterator ohne ConcurrentModificationException zu implementieren.
\end{itemize}
\end{frame}


\begin{frame}\frametitle{Optimierungen: kd-Tree}
\begin{itemize}
\item Dreiecke müssen leer sein, um für eine Triangulierung in Frage zu kommen.
\item Beim Erzeugen eines Dreiecks muss geprüft werden, ob sich kein Punkt innerhalb des Dreiecks befindet.
\item Beim Test der Diamond Property müssen ebenfalls Punkte innerhalb von Dreiecken gefunden werden.
\item Wir möchten nicht für jedes Dreieck jeweils alle Punkte überprüfen müssen.
\item Wir haben uns für einen kd-Baum als Punktdatenstruktur entschieden.
\end{itemize} 
\end{frame}

\begin{frame}\frametitle{Optimierungen: kd-Tree}
\vspace{-.2cm}
\includegraphics<1>[scale=0.25]{../../documentation/images/kdSearch3D.pdf}\\
\vspace{-.3cm}
\includegraphics<1>[scale=0.25]{../../documentation/images/kdSearch2D.pdf}
\end{frame}

\begin{frame}\frametitle{Optimierungen: kd-Tree}
\includegraphics<1>[scale=0.7]{../../documentation/images/kdSearchRange.pdf}
\begin{itemize}
\item Kd-Bäume erlauben orthogonale Bereichssuche in $O(\sqrt{n} + k)$ Zeit im ungünstigen Fall.
\item Wenn der Suchbereich günstig ist, ist die erwartete Laufzeit wesentlich besser.
\end{itemize} 
\end{frame}


\begin{frame}\frametitle{Optimierungen: kd-Tree}
\includegraphics<1>[scale=0.7]{../../documentation/images/kdSearchRangePretest.pdf}
\begin{itemize}
\item Wir suchen zunächst nach Punkten innerhalb eines relativ kleinen Bereichs, das sich innerhalb des Dreiecks befindet.
\item Nur wenn sich dort keine Punkte befinden, müssen wir noch den gesamten Bereich des Dreiecks testen.
\end{itemize} 
\end{frame}

\begin{frame}\frametitle{Optimierungen: kd-Tree}
\begin{itemize}
\item Es gibt andere Datenstrukturen, die schnellere Bereichssuche erlauben, z.B.:
\begin{itemize}
\item Range Trees
\item Cutting Trees
\end{itemize}
\item Andere Implementierungen haben einen Bucketing-Ansatz gewählt.
\end{itemize} 
\end{frame}

\begin{frame}\frametitle{Optimierungen: Multithreading}
\begin{itemize}
\item Wir haben zwei Teile des LMT-Algorithmus parallelisiert:
\begin{itemize}
\item \vspace{5pt}Das Erzeugen der Kandidatenkanten. Dieser Teil benötigt einen signifikanten Teil der Laufzeit und beinhaltet auch den Diamond Test.
\item \vspace{5pt}Das Überprüfen der lokal minimalen Kanten auf Überschneidungen.
\end{itemize}
\end{itemize} 
\end{frame}

\begin{frame}\frametitle{Optimierungen}
\includegraphics<1>[scale=0.27]{../../documentation/images/MWT_benchmarks_graph.pdf} 
\end{frame}